package Cluedo.Game;

import java.util.Vector;
import java.util.Hashtable;

/**
 * An essential class for the Game model, this stores all nodes in the graph representing the board.
 * it also performs all search operations.
 *  
 * @author Alex Ellis
 *
 */
public class Map {
	private Board lnkBoard;

	/**
	 * All existing nodes in the game.
	 * 
	 */
	Vector positions = new Vector();
	
	Position foundPosition = null;
	
	/**
	 *  Used in shortest path functions
	 */
	int shortestPath = -1;
	/**
	 *  Used in shortest path functions
	 */
	Vector shortestPathRoute = new Vector();
	/**
	 * 	Used in shortest path functions
	 */
	boolean pathFound = false;
	int mapDebug = 0;
	
	/**
	 * Get all the map nodes in the game.
	 * 
	 * @param type
	 * specify "rooms" or "" for all
	 * @return the nodes in the map
	 */
	public Vector getNodes(String type) {
		Vector result = new Vector();

		if(type.equals("rooms")) {
			result = vectorCopy( positions );
			for(int i = 0; i < positions.size(); i++)
				if(!(positions.elementAt(i) instanceof Room))
					result.remove(positions.elementAt(i));
			return result;
		}
		return positions;
	}
	/**
	 * @return Simply all nodes in map.
	 */
	public Vector getNodes() {
		return positions;
	}
	public void setNodes(Vector nodes) {
		positions = vectorCopy(nodes);
	}
	
	  /**
	   * Does what it says on the tin.
	   * @param passedNodes
	   * @return a new vector
	   */
	  public Vector vectorCopy(Vector passedNodes) {
		 	Vector vcopy = new Vector();
		 	for(int i = 0; i < passedNodes.size(); i++)
		 		vcopy.add(passedNodes.elementAt(i));
		 	
		 	return vcopy;
	  }


	/**
	 * Searches all positions and returns an object based on its ID
	 * 
	 * @param ID The name of the node to search.
	 * @return Position corresponding to ID 
	 */
	 public Position findByID(String ID) {
	  	for(int i = 0; i < positions.size(); i++)
	 		if(((Position) positions.elementAt(i)).getID().equals(ID)) {
	 			return (Position) positions.elementAt(i);
	 		}
	 		
		return null;
	 }
	 /**
	  * Binding is reciprocal and joins to nodes together.
	  * 
	  * @param target
	  * Source
	  * @param bind
	  * Target
	  */
	 public void bind(String target, String bind) {
	 	// Binding is reciprocal
	 	Position targetPointer = findByID(target);
	 	Position bindPointer = findByID(bind);

	 	if(targetPointer != null && bindPointer != null) {
	 		targetPointer.addNeighbour(bindPointer);
	 		bindPointer.addNeighbour(targetPointer);
	 	}
	 }

	private void printPath(Vector pathTaken) {
		for(int i =0;i<pathTaken.size();i++)
			System.out.print(
				((Position)pathTaken.elementAt(i)).getID() + " > "
				);

		System.out.print("\n");	
	}

	// Holds backwards mappings from the destination node.
	Hashtable fathers;

	/**
	 * Finds the shortest legal path ( according to the cluedo rules )
	 * in the graph G from node src to node dest returning a vector of the route taken.
	 *
	 * @param src
	 * Node to start search from
	 * @param dest
	 * Node to stop search at
	 * @return a vector of the path taken
	 */
	public Vector routeTo(Position src, Position dest) {
		Vector queue = new Vector();
		Vector passed = new Vector();
 		fathers = new Hashtable();
 		
		passed.add(src);
				

		for(int i =0;i<src.getNeighbours().size();i++) {
			Position u = (Position)src.getNeighbours().elementAt(i);
			if(u.isOccupied() == true && !( u instanceof Room)) {
				passed.add(u);
				continue;
			}
			fathers.put(u.getID(), src);
			queue.add(u);
		}
		
		int len = validPathTo(src,dest,queue,passed);

		// Trace-back all the fathers of nodes and build a path
				
		Vector pathTaken = new Vector();
		
		Position trace = (Position)fathers.get(dest.getID());
		pathTaken.add(0,dest);
		while(trace != null && trace!=src) {
			pathTaken.add(0, trace);
			trace = (Position)fathers.get(trace.getID());
		}
		if(trace == null) {
//			System.out.println("no route exists");
			return new Vector();
		}
		
		
		pathTaken.add(0,src);

		return pathTaken;
	}
	
	/**
	 * Finds the shortest illegal path ( NOT according to the cluedo rules )
	 * in the graph G from node src to node dest returning a vector of the route taken.
	 *
	 * @param src
	 * Node to start search from
	 * @param dest
	 * Node to stop search at
	 * @return a vector of the path taken
	 */
	public Vector illegalRouteTo(Position src, Position dest) {
		Vector queue = new Vector();
		Vector passed = new Vector();
 		fathers = new Hashtable();
 		
		passed.add(src);
				

		for(int i =0;i<src.getNeighbours().size();i++) {
			Position u = (Position)src.getNeighbours().elementAt(i);

			fathers.put(u.getID(), src);
			queue.add(u);
		}
		
		int len = illegalPathTo(src,dest,queue,passed);

		// Trace-back all the fathers of nodes and build a path
				
		Vector pathTaken = new Vector();
		
		Position trace = (Position)fathers.get(dest.getID());
		pathTaken.add(0,dest);
		while(trace != null && trace!=src) {
			pathTaken.add(0, trace);
			trace = (Position)fathers.get(trace.getID());
		}
		if(trace == null) {
//			System.out.println("no route exists");
			return new Vector();
		}
		
		
		pathTaken.add(0,src);

		return pathTaken;
	}
	
	
	
	/**
	 * Finds the shortest illegal path (NOT according to the cluedo rules)
	 * in the graph G from node src to node dest.
	 *
	 * Note: traversal is breadth-first and based on dijkstra's algorithm.
         *
	 * @return the size of the path
	 * @param src
	 * Node to start search from
	 * @param dest
	 * Node to stop search at
	 * @param queue
	 * Queue of nodes to traverse
	 * @param passed
	 * List of nodes not to revisit
	 *
	 */
	public int illegalPathTo(Position src, Position dest, Vector queue, Vector passed) {
		int qSize = queue.size();

		Position n;		// Node being examined
		Position u;		// Adjacent node (neighbour)
		Vector neighbours; 	// List of neighbours for n

		if(qSize == 0)
			return 0;

		while(qSize > 0) {
			// Grab from queue
			n = (Position)queue.firstElement();

			if(n == dest)
				return 1;
			
			// find neighbours of item
			neighbours = n.getNeighbours();

			if(!passed.contains(n)) {
				// traverse all neighbours of queue
				for(int j=0;j<neighbours.size();j++) {
					u = (Position)neighbours.elementAt(j);
					// add all neighbours to queue
					if(passed.contains(u) == false && queue.contains(u) == false) {

						queue.add(u);
						fathers.put(u.getID(), n);
					}
				}
			}

			// mark this as viewed
			passed.add(n);

			// take item out of queue
			queue.remove(queue.firstElement());
			qSize--;

		}
		return illegalPathTo(src, dest, queue, passed) + 1;
	}

	// temporary debug variable
	 final static String testCase = "I16";
	 
	/**
	 * Finds the shortest legal path (according to the cluedo rules)
	 * in the graph G from node src to node dest.<p>
	 *
	 * Note: traversal is breadth-first and based on dijkstra's algorithm.
	 *
	 * @return the size of the path
	 * @param src
	 * Node to start search from
	 * @param dest
	 * Node to stop search at
	 * @param queue
	 * Queue of nodes to traverse
	 * @param passed
	 * List of nodes not to revisit
	 *
	 */
	public int validPathTo(Position src, Position dest, Vector queue, Vector passed) {
		int qSize = queue.size();
		boolean tryOtherRoute = false; 
		
		Position n;		// Node being examined
		Position u;		// Adjacent node (neighbour)
		Vector neighbours; 	// List of neighbours for n

		if(qSize == 0)
			return 0;

		while(qSize > 0) {
			// Grab from queue
			n = (Position)queue.firstElement();

			if(n == dest)
				return 1;
	
			// find neighbours of item
			neighbours = n.getNeighbours();

			if (!passed.contains(n)) {
				// traverse all neighbours of queue
				for (int j = 0; j < neighbours.size(); j++) {
					u = (Position) neighbours.elementAt(j);
					
					// add all neighbours to queue
					if (passed.contains(u) == false && queue.contains(u) == false) {
						boolean badLink = false;

						
						/**
						 * When src is a room then
						 * Intermediate rooms MUST be ultimate node.
						 */
						if(src instanceof Room) {
							if(u instanceof Room && u != dest) {
								badLink = true;
								if(u.getID().equals(testCase)) {
									System.out.println("Fail at 0 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
								}
							}
						}
						/**
						 * If next node is room and isn't the destination.
						 */
						if(u instanceof Room == true) {
							if(u != dest) {
								badLink=true;
								if(u.getID().equals(testCase)) {
									System.out.println("Fail at 1 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
								}

							}
						}
						
						/**
						 * If next node is room and isn't the destination or source.
						 */
						if(n instanceof Room && (n != src && n != dest)) {
							badLink=true;
							// Try another route to get here and don't disguard the node completely
							tryOtherRoute =true;
							if(u.getID().equals(testCase)) {
								System.out.println("Fail at 2 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() + " n=" + n.getID()  );
							}

						}
						
						/**
						 * Any starting-/square occupied not allowed
						 */
						if (u instanceof Square == true || u instanceof StartingSquare == true) {
							if(u.isOccupied() == true) {
								badLink = true;
								if(u.getID().equals(testCase)) {
									System.out.println("Fail at 3 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
								}

							}
						}
						
						
						if(u instanceof Room) {
							
							/** Room that isn't destination **/
							if(u != dest) {
								badLink=true;
								if(u.getID().equals(testCase)) {
									System.out.println("Fail at 4 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
								}

							}

							if(n instanceof Room == true) {
								/*
								 * Room to room transition only allowed if N == SRC and
								 * U == DEST
								 */
								if (n != src && u != dest) {
									badLink = true;			
									if(u.getID().equals(testCase)) {
										System.out.println("Fail at 5 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
									}
	
								}
								
							}
						}

						/** Going from square to room
						 *  Room must b source and n not the source **/
						if ((u instanceof StartingSquare == true || u instanceof Square == true) && n instanceof Room == true) {
							if (src instanceof Room == true && n != src) {
								badLink = true;
								if(u.getID().equals(testCase)) {
									System.out.println("Fail at 6 id=" + u.getID()  + ", o=" + u.isOccupied() + ", t=" +u.getClass().getName() );
								}
	
							}
						}


						/** Bad links are added into the pased vector so we don't visit them again */
						if (badLink == true) {
							if(tryOtherRoute == false)
								passed.add(u);

						}
						else {
							/** Valid links are added into the search queue and the father is set node */
							queue.add(u);
							fathers.put(u.getID(), n);
						}
					}
				}
			}

			// mark this as viewed
			passed.add(n);

			// take item out of queue
			queue.remove(queue.firstElement());
			qSize--;

		}
		return validPathTo(src, dest, queue, passed) + 1;
	}
}
